package flashBack;

/**
 * @author zxc
 * @date 2023/01/17 11:38
 **/

import java.util.LinkedList;
import java.util.List;

/**
 *  题目 ：生成匹配的括号
 *  题目详述 :
 *  正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class GenerateParenthesis {
    public List<String> generateParenthesis(int n) {
        List<String> result = new LinkedList<>();
        /**
         *  参数分析 ：
         *  （1）第一个参数 ：left所存储的是，剩余需要去生成的左括号数量;
         *  （2）第二个参数 ：right所存储的是，剩余需要去生成的右括号数量;
         *  （3）第三个参数 ：所传入的result集合
         */
        flushBack(n , n , "" ,result);
        return result;
    }

    private void flushBack(int left, int right,
                           String s, List<String> result) {
        // 若是left == 0 && right == 0的话，
        // 即代表题目所要求的n个左括号和n个右括号都已经加入到字符串s中，形成了有效的括号组合;
        if(left == 0 && right == 0){
            result.add(s);
            // 若是满足了 left == 0 && right == 0的条件时，则不需要再继续向下递归;
            // 其实不使用return也是可以的，但是会出现无效遍历;
            // ===》 所以回溯法的“剪枝”操作是必要的;
            return ;
        }
        // 在满足限制条件[（1）左括号/右括号数目 <= n && （2）同时满足括号的匹配（即，右括号数目 <= 左括号数目）]下，
        // ===》 使用回溯法，获取所有有效的括号组合;
        if(left > 0){
            //（1）左括号/右括号数目 <= n;
            flushBack(left - 1 , right , s + "(" , result);
        }
        if(right > left){
            // 同时满足括号的匹配（即，右括号数目 <= 左括号数目）;
            flushBack(left , right - 1 , s + ")" , result);
        }
    }
}
